package com.cat.graphTheory;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/shortest-distance-after-road-addition-queries-i/
 * @create 2025/9/19 19:17
 * @since JDK17
 */

public class Solution13 {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        int m = queries.length;
        int [] ans = new int[m], dis = new int[n];
        Queue<Integer> q = new ArrayDeque<>();
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {   // 建立最初的
            g[i].add(i + 1);
        }

        for (int i = 0; i < m; i++) {
            int from = queries[i][0], to = queries[i][1];
            g[from].add(to);
            Arrays.fill(dis, -1);
            q.offer(0);
            dis[0] = 0;
            while (q.size() != 0) {
                int x = q.poll();
                for (int y : g[x]) {
                    if (dis[y] < 0) {
                        dis[y] = dis[x] + 1;
                        q.offer(y);
                    }
                }
            }
            ans[i] = dis[n - 1];
        }

        return ans;
    }
}
